def partition(nums, left, right):
    pivot = nums[0]
    while left < right:
        while left < right and nums[right] >= pivot:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= pivot:
            left += 1
        nums[right] = nums[left]
    # 下面两行命令的left可以变为right，因为此时两者已相等
    nums[left] = pivot
    return left


def qsort(nums, left, right):
    if left >= right:
        return
    mid = partition(nums, left, right)
    qsort(nums, left, mid-1)
    qsort(nums, mid+1, right)


def quick_sort(nums):
    qsort(nums, 0, len(nums)-1)


if __name__ == "__main__":
    nums = [5, 2, 4, 1, 3]
    quick_sort(nums)
    print(nums)
